﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Qiang.QMath
{
    /// <summary>
    /// 具有优先级的队列
    /// 这里的优先级是用距离来定义的，即一个double值
    /// 用数组（堆）实现队列（二叉树），而不是链表。实际上这是一个完全二叉树
    /// </summary>
    public class KdQueue
    {

        //注意：
        //一个队列的实际元素数要比其个数大1，比如其个数this._count=1，则其实际存了两个元素，
        //因为队列的第一个位置存储了一个特殊的元素表示最大或最小优先级的元素

        //其实这个队列只是保证第一个元素是最高优先级了并且父层大于子层，不能保证左侧大于右侧
        //，每添加一个元素在最后一层，然后与其父层比较优先级大小(不与其同一层的枝叶进行比较，这样同一层的优先级顺序可能不正确)，
        //最终会比较到第一层，而第一层在二叉树中只有一个数据。所以说只保证第一层即第一个数据是最高优先级了.
        //可能因为这样就满足需求了，不需要靠前的元素一定要大于靠后的元素。
        //如果要满足靠前的优先级大于靠后的，则直接排序数组就行，只是这样效率就低很多、、、

        //  这里的优先级是指优先出列

        // 这个添加方法能保证父层比子层大，但不能保证左树叶比右树叶大
        //所以删除方法时用到是BubbleDown()方法也得保证第一个元素是最高优先级，这时不但要将父层与子层比大小，还要先比较子层中左右树叶谁大谁与你层比，并交换父子层位置。


        # region 构造方法

        public KdQueue()
        {
            this.Init(20);
        }

        public KdQueue(int capcity)
        {
            this.Init(capcity);
        }

        public KdQueue(int capcity, double maxPriority)
        {
            this._maxPriority = maxPriority;
            Init(capcity);
        }


        /// <summary>
        /// 初始化。第一个位置存储特殊元素
        /// </summary>
        /// <param name="capacity"></param>
        private void Init(int capacity)
        {
            this._capacity = capacity;
            this._data = new object[this._capacity + 1];
            this._priorityValues = new double[this._capacity + 1];
            this._data[0] = null;
            this._priorityValues[0] = this._maxPriority;
        }

        # endregion



        //最高优先级
        private readonly double _maxPriority = double.MaxValue;

        private object[] _data; //存储数据，值

        private double[] _priorityValues; //存储指示优先级的值，在这里是距离

        private int _count; //队列的个数

        private int _capacity;  //队列的容量，能空下多少个数据



        /// <summary>
        /// 添加一个新元素
        /// 这个添加方法能保证父层比子层大，但不能保证左树叶比右树叶大
        /// </summary>
        /// <param name="data"></param>
        /// <param name="priority"></param>
        public void Add(object data, double priority)
        {
            //如果队列的个数超出了队列的容量，则扩展队列
            if (this._count++ >= this._capacity)
            {
                this.ExpandCapacity();
            }

            //先将新元素添加到队列的最后一位
            this._data[this._count] = data;
            this._priorityValues[this._count] = priority;

            //因为新添加的元素暂时放在了最后一位，所以要将新添加的元素按其优先级向上移动合适的位置
            this.BubbleUp(this._count);

        }

        /// <summary>
        /// 把第一个元素（即优先级最高的）移走出列
        /// </summary>
        /// <returns></returns>
        public object Remove()
        {
            if (this._count == 0) return null;

            object element = this._data[1];  //取出第一个元素,记住这里索引不是0

            //将最后一个元素赋给第一个
            this._data[1] = this._data[this._count];
            this._priorityValues[1] = this._priorityValues[this._count];

            //最后一个元素赋空，
            this._data[this._count] = null;
            this._priorityValues[this._count] = 0L;

            //队列个数减1
            this._count--;

            //将第一个元素向下移找到其合适的位置
            this.BubbleDown(1);

            return element;
        }


        /// <summary>
        /// 扩展队列的容量
        /// 一般情况下建议给队列分配足够的容量，因为调用这个方法太昂贵了
        /// </summary>
        private void ExpandCapacity()
        {
            //扩展
            this._capacity = this._count * 2;
            object[] elements = new object[this._capacity + 1];
            double[] prioritys = new double[this._capacity + 1];
            //复制
            Array.Copy(this._data, 0, elements, 0, this._data.Length);
            Array.Copy(this._priorityValues, 0, elements, 0, this._priorityValues.Length);
            //重新赋值
            this._data = elements;
            this._priorityValues = prioritys;
        }



        /// <summary>
        /// 将指定位置的元素放上移到适合其优先级的位置
        /// </summary>
        /// <param name="pos"></param>
        private void BubbleUp(int pos)
        {
            object element = this._data[pos];
            double priorty = this._priorityValues[pos];

            while (this._priorityValues[pos / 2] < priorty) //有数组存储二叉树，所以父节点的位置始终是子节点位置的1/2
            {
                this._priorityValues[pos] = this._priorityValues[pos / 2];
                this._data[pos] = this._data[pos / 2];
                pos = pos / 2;
            }

            this._priorityValues[pos] = priorty;
            this._data[pos] = element;

        }

        /// <summary>
        /// 将指定位置的元素放下移到适合其优先级的位置
        /// </summary>
        /// <param name="pos"></param>
        private void BubbleDown(int pos)
        {
            object element = this._data[pos];
            double priority = this._priorityValues[pos];

            //pos位置所在层为父层

            int child;  //child位置所在层为子层

            while (pos * 2 <= this._count)
            {
                child = pos * 2;

                if (child != this._count) //如果child等于队列的个数，那么当前父层只有一个叶子
                {
                    if (this._priorityValues[child] < this._priorityValues[child + 1]) //比较当前子层两个叶子谁大谁小，谁优先级大谁与父层比较
                    {
                        child++;
                    }
                }

                if (priority < this._priorityValues[child]) //如果父层优先级小于子层中较大的优先级，则将子层数据赋给
                {
                    this._priorityValues[pos] = this._priorityValues[child];
                    this._data[pos] = this._data[child];

                    pos = child;  //父层的位置跑到子层，重新定义父层位置
                }
                else  //如果父层优先级大于子层中所有优先级，则找到了合适的位置，结束循环
                {
                    pos = child;   //父层的位置跑到子层，重新定义父层位置
                    break;
                }
            }

            this._data[pos] = element;
            this._priorityValues[pos] = priority;

        }


        public void Clear()
        {
            //队列的清空怎么写呢，存储数据的data里面每个数据可以置成null，可是存储优先级的_priorityValues怎么清空呢，看来需要一个无效值
            //或者每次用0

            for (int i = 1; i <= this._count; i++)
            {
                this._data[i] = null;
                this._priorityValues[i] = 0L;
            }

            this._count = 0;

        }


        /// <summary>
        /// 取得本队列的最大优先级
        /// </summary>
        /// <returns></returns>
        public double GetMaxPriority()
        {
            return this._priorityValues[0];
        }


        public int Length()
        {
            return this._count;
        }


    }
}
